// Heap Class type //
//#include "queue.h"

class queue;

class PQType;

struct weightedpixel{

	weightedpixel();
	bool operator >=( const weightedpixel & );
	bool operator <=( const weightedpixel & );
	bool operator < ( const weightedpixel & );
	bool operator ==( const weightedpixel & );
	bool operator > ( const weightedpixel & );
	weightedpixel &operator = ( const weightedpixel & );
	void set( const int&, const int& , const bool& );

	int weight;
	int pixelval;
	bool isLeaf;
	weightedpixel* left;
	weightedpixel* right;
};

class queue{
  public:
    queue(int);
    ~queue();
    void makeEmpty();
    bool isEmpty()const;
    bool isFull()const;
    void Enqueue( weightedpixel );
    void Dequeue( weightedpixel & );
    void print();
    
  private:
    int front, rear, maxQueue; 
    weightedpixel *items;
    
};
////////////////////// WEIGHTED PIXEL FUNCTIONS ////////////////////////////////

weightedpixel::weightedpixel()
{
	weight = 0;
	pixelval = -1;
	isLeaf = true;
	right = NULL;
	left = NULL;
}

bool weightedpixel::operator >=( const weightedpixel &rhs )
{
	return( weight >= rhs.weight );
}

bool weightedpixel::operator <=( const weightedpixel &rhs )
{
	return( weight <= rhs.weight );
}
bool weightedpixel::operator < (const weightedpixel &rhs )
{
	return( weight < rhs.weight );
}
bool weightedpixel::operator ==( const weightedpixel &rhs )
{
	return( weight == rhs.weight );
}
bool weightedpixel::operator > ( const weightedpixel &rhs )
{
	return( weight > rhs.weight );
}
weightedpixel &weightedpixel::operator = ( const weightedpixel &rhs )
{
	if( this != &rhs )
	{
		weight = rhs.weight;
		pixelval = rhs.pixelval;
		right = rhs.right;
		left = rhs.left;		
	}
	return *this;
}

void weightedpixel::set(const int & weight_2, const int & pixelval_2,const bool & isleaf_2 )
{
	weight = weight_2;
	pixelval = pixelval_2;
	isLeaf = isleaf_2;

}


////////////////////////////////////////////////////////////////////////////////
class tree{
public:
	
	tree();
	bool operator <= (const tree & );
	bool operator >= (const tree & );
	bool operator < (const tree & );
	bool operator == (const tree & );
	bool operator > (const tree & );
	tree &operator = (const tree & );
	void preOrder( queue &, const weightedpixel *  ); 
	// left tree is the new tree created
	void merge( const tree & );
	void print(queue &, const weightedpixel *);

//private: 
	weightedpixel *tip;
	
};

tree::tree()
{
	tip = new weightedpixel;
}
bool tree::operator >= (const tree &rhs )
{
	return( *tip >= (*rhs.tip) );
}


bool tree::operator <= (const tree &rhs )
{
	return( *tip <= (*rhs.tip) );
}
bool tree::operator < (const tree &rhs )
{
	return( *tip < (*rhs.tip ) );
}
bool tree::operator == (const tree &rhs )
{
	return( *tip == (*rhs.tip ) );
}
bool tree::operator > (const tree &rhs )
{
	return( *tip > (*rhs.tip ) );
}
tree &tree::operator = (const tree &rhs )
{
	*tip = (*rhs.tip);
	return *this;
}

void tree::preOrder( queue &preQue, const weightedpixel *Tree )
{
	if( Tree != NULL )
	{
		if( (*Tree).isLeaf )
		{		
			preQue.Enqueue( *Tree );		
		}
		else
		preOrder( preQue, Tree->left );
		preOrder( preQue, Tree->right );
	}

}


void tree::merge( const tree & rhs )
{
	weightedpixel* temp;

	weightedpixel* righttree;
	righttree = rhs.tip;

	temp = new weightedpixel;
	temp->set( 0, -1, false );
	temp->left = NULL;
	temp->right = NULL;

	temp->weight = tip->weight + righttree->weight;
	temp->isLeaf = false;

	temp->left = tip;
	temp->right = righttree;
	tip = temp;
}

void tree::print(queue &preQue, const weightedpixel *Tree )
{
	preOrder( preQue, Tree );
}


//////////////////////////////////////////////////////////////////////////////////



struct HeapType{

	void ReheapDown( int, int);
	void ReheapUp(int, int );
	void Swap( tree*, int, int );/////////////////////////////////////////

	tree* elements;// dynamic array of leafs
	int numElements;
};


void HeapType::ReheapDown(int root, int bottom)
{
	int maxChild, rightChild, leftChild;
	
	leftChild = 2*root+1;
	rightChild = 2*root+2;
	
	if(leftChild <= bottom) {  // left child is part of the heap
		if(leftChild == bottom) // only one child
			maxChild = leftChild;
		else { // two children
			if(elements[leftChild] >= elements[rightChild])
				maxChild = rightChild;
			else
				maxChild = leftChild;
		}
		if(elements[root] > elements[maxChild]) {// compare max child with parent
			Swap(elements, root, maxChild);
			ReheapDown(maxChild, bottom);
		}
	}
} 


void HeapType::ReheapUp(int root, int bottom)
{
	int parent;
	
	if(bottom > root) { // tree is not empty
		parent = (bottom-1)/2;
		if(elements[parent] > elements[bottom]) {
			Swap(elements, parent, bottom);
			ReheapUp(root, parent);
		}
	}
} 

void HeapType::Swap( tree *T, int parent, int bottom )
{
	tree temp;

	temp = elements[parent];
	elements[parent] = elements[bottom];
	elements[bottom] = temp;
	
}	

// heap Fucntions


// Priority queue Imlementation


class PQType {
public:
	PQType(int);
	~PQType();
	void MakeEmpty();
	bool IsEmpty() const;
	bool IsFull() const;
	void Enqueue(tree);
	void Dequeue(tree&);
	void print();
//private:
	int numItems; // num of elements in the queue
	HeapType heap;
	int maxItems; // array size
}; 


PQType::PQType(int max)
{
	maxItems = max;
	heap.elements = new tree[max];
	numItems = 0;
}

PQType::~PQType()
{
	delete [] heap.elements;
}

void PQType::Dequeue(tree & item)
{
	item = heap.elements[0];
	heap.elements[0] = heap.elements[numItems-1];
	numItems--;
	heap.ReheapDown(0, numItems-1);
}

void PQType::Enqueue(tree newItem)
{
	numItems++;
	heap.elements[numItems-1] = newItem;
	heap.ReheapUp(0, numItems-1);
}

void PQType::MakeEmpty()
{
	numItems = 0;
}

bool PQType::IsEmpty() const
{
	return numItems == 0;
}

bool PQType::IsFull() const
{
	return numItems == maxItems;
}

void PQType::print()
{
	int index = 0;
	
	while( index < numItems )
	{
		cout << "Pixel: " << (*heap.elements[index].tip).pixelval;
		cout << " Weight: " << (*heap.elements[index].tip).weight << endl;
		index++;
	}
}


/////////////////////////////////////////////////////////////////////////


queue::queue( int max )
{
    maxQueue = max + 1;
    front = maxQueue - 1;
    rear = maxQueue - 1;
    items = new  weightedpixel[maxQueue];
}

queue::~queue()
{
    delete [] items;
}

void queue::makeEmpty()
{
    front = maxQueue - 1;
    rear = maxQueue - 1;
}

bool queue::isEmpty()const
{
    return (rear == front );
}

bool queue::isFull()const
{
    return( (rear + 1 ) % maxQueue == front );
}

void queue::Enqueue( weightedpixel NewItem)
{
    rear = (rear + 1) % maxQueue;
    items[rear] = NewItem;
}

void queue::Dequeue( weightedpixel &item )
{
    front = (front+1) % maxQueue;
    item = items[front];
}

    int front, rear, maxQueue; 
    weightedpixel *items;


void queue::print()
{
	weightedpixel temp;
	
	while( !isEmpty() )
	{
		Dequeue( temp );
		cout << "PixelVal: " << temp.pixelval << " Weight: " << temp.weight << endl;
	}
}
